import java.util.*;

public class LCP7 {
    public static void main(String[] args) {
        int n = 5;
        int[][] relation = {{0, 2}, {2, 1}, {3, 4}, {2, 3}, {1, 4}, {2, 0}, {0, 4}};
        int k = 3;

        System.out.println(numWays(n, relation, k));
    }

    public static int numWays(int n, int[][] relation, int k) {
        int[][] f = new int[k + 1][n];
        f[0][0] = 1;
        for (int i = 1; i <= k; i++) {
            for (int[] r : relation) {
                int a = r[0], b = r[1];
                f[i][b] += f[i - 1][a];
            }
        }
        return f[k][n - 1];
    }

    static Map<Integer, Set<Integer>> map1 = new HashMap<>();
    static int nn1, kk1, res1;

    public static int numWaysDFS(int n, int[][] relation, int k) {
        nn1 = n;
        kk1 = k;
        for (int[] r : relation) {
            int a = r[0], b = r[1];
            Set<Integer> set = map1.getOrDefault(a, new HashSet<>());
            set.add(b);
            map1.put(a, set);
        }
        dfs(0, 0);
        return res1;
    }

    public static void dfs(int u, int sum) {
        if (sum == kk1) {
            if (u == nn1 - 1) {
                res1++;
            }
            return;
        }
        Set<Integer> es = map1.get(u);
        if (es == null) {
            return;
        }
        for (int next : es) {
            dfs(next, sum + 1);
        }
    }

    public static int numWaysBFS(int n, int[][] relation, int k) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] r : relation) {
            int a = r[0], b = r[1];
            Set<Integer> set = map.getOrDefault(a, new HashSet<>());
            set.add(b);
            map.put(a, set);
        }
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addLast(0);
        while (!deque.isEmpty() && k-- > 0) {
            int size = deque.size();
            while (size-- > 0) {
                int poll = deque.poll();
                Set<Integer> es = map.get(poll);
                if (es == null) {
                    continue;
                }
                for (int next : es) {
                    deque.addLast(next);
                }
            }
        }
        int res = 0;
        while (!deque.isEmpty()) {
            if (deque.pollFirst() == n - 1) {
                res++;
            }
        }
        return res;
    }
}
